#include "tools.h"
using std::sort;




class Solution {
public:
    vector<vector<int>> twoSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        // 双指针，需要数列有序
        sort(nums.begin(), nums.end());
        int lo = 0, hi = nums.size() - 1;
        while (lo < hi){
            int sum = nums[lo] + nums[hi];
            if (sum == target){
                res.push_back({nums[lo], nums[hi]});
                // 跳过重复元素
                int left = nums[lo];
                int right = nums[hi];
                while (lo < hi && nums[lo] == left) ++lo;
                while (lo < hi && nums[hi] == right) --hi;
            }
            else if (sum < target) ++lo;
            else if (sum > target) --hi;
        }
        return res;
    }
};


int main(int argc, char const *argv[])
{
    vector<int> arr = {1,3,1,2,2,3};
    showList(arr);

    Solution s;
    vector<vector<int>> res = s.twoSum(arr, 4);
    for (int i = 0; i < res.size(); ++i)
        showList(res[i]);




    return 0;
}
